/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-01
 * Time: 21:53
 */
public class SearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    //插入一个元素
    public boolean insert(int key) {
        TreeNode node=new TreeNode(key);
        if(root==null){
            root=node;
            return true;
        }
        TreeNode p=root;
        TreeNode p2=root;
        while(p!=null){
            if(key<p.key){
                p2=p;
                p=p.left;
            }
            else if(key>p.key){
                p2=p;
                p=p.right;
            }
            else{
                System.out.println("插入元素重复");
                return false;
            }
        }
        if(key<p2.key){
            p2.left=node;
        }
        else{
            p2.right=node;
        }
        return true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
        if(root==null){
            return null;
        }
        TreeNode p=root;
        while(p!=null){
            if(key<p.key){
                p=p.left;
            }
            else if(key>p.key){
                p=p.right;
            }
            else{
                return p;
            }
        }
        return null;
    }

    //删除key的值
    public boolean remove(int key) {
        if(root==null){
            System.out.println("树为空，无法删除");
            return false;
        }
        TreeNode p=root;
        TreeNode p2=root;
        while(p!=null){
            if(key<p.key){
                p2=p;
                p=p.left;
            }
            else if(key>p.key){
                p2=p;
                p=p.right;
            }
            else{
                break;
            }
        }
        if(p==null){
            System.out.println("树中没有该元素");
            return false;
        }
        fun(p,p2);

        return false;
    }
    public void fun(TreeNode p,TreeNode p2){
        if(p.left==null){
            if(p==root){
                root=p.right;
            }
            else if(p==p2.left){
                p2.left=p.right;
            }
            else if(p==p2.right){
                p2.right=p.right;
            }
        }
        else if(p.right==null){
            if(p==root){
                root=p.left;
            }
            else if(p==p2.left){
                p2.left=p.left;
            }
            else if(p==p2.right){
                p2.right=p.left;
            }
        }
        else{
            TreeNode s=p.left;
            TreeNode s2=p;
            while(s.right!=null){
                s2=s;
                s=s.right;
            }
            p.key=s.key;
            fun(s,s2);
        }
    }
}
